/*
 * mm-naive.c - The fastest, least memory-efficient malloc package.
 * 
 * In this naive approach, a block is allocated by simply incrementing
 * the brk pointer.  A block is pure payload. There are no headers or
 * footers.  Blocks are never coalesced or reused. Realloc is
 * implemented directly using mm_malloc and mm_free.
 *
 * NOTE TO STUDENTS: Replace this header comment with your own header
 * comment that gives a high level description of your solution.
 */
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <unistd.h>
#include <string.h>

#include "mm.h"
#include "memlib.h"
/*********************************************************
 * NOTE TO STUDENTS: Before you do anything else, please
 * provide your team information in the following struct.
 ********************************************************/
team_t team = {
    /* Team name */
    "TJU",
    /* First member's full name */
    "3022206130 2024.12.14",
    /* First member's email address */
    "student@tju.edu.cn",
    /* Second member's full name (leave blank if none) */
    "",
    /* Second member's email address (leave blank if none) */
    ""
};

static char *heap_list;
static char *global_ptr;
// MAX MIN方法
#define MAX(x, y) ((x) > (y) ? (x) : (y))
#define MIN(x, y) ((x) < (y) ? (x) : (y))

// 数字宏 
#define WSIZE 4 // 单字
#define DSIZE 8 // 双字
#define CHUNKSIZE  512 // 初始堆大小
#define ALLOCATED 1 // 已分配BOOL值
#define FREE 0 // 未分配BOOL值
#define SEG_LEN 15 // 大小类总类数
#define ALIGNMENT 8 //对齐边界

// GET SET COMBINE ALIGN方法
#define GET(p) (*(unsigned int *)(p))
#define SET(p, val) (*(unsigned int *)(p) = (unsigned int)val) // 在 p 地址处读写一个字
#define COMBINE(size, alloc) ((size) | (alloc))
#define ALIGN(size) (((size) + (ALIGNMENT - 1)) & ~0x7)

// 获取 Size 和 Alloc 值
#define GET_SIZE(p) (GET(p) & ~0x7)
#define GET_ALLOC(p) (GET(p) & 0x1)

// 获取 header 和 footer
#define GET_HD(bp) ((char *)(bp) - WSIZE) // HEADER
#define GET_FT(bp) ((char *)(bp) + GET_SIZE(GET_HD(bp)) - DSIZE) //FOOTER

// 获得给定块的前驱或后继块及其大小
#define GET_NEXT(bp) ((char *)(bp) + GET_SIZE(GET_HD(bp)))
#define GET_PREV(bp) ((char *)(bp) - GET_SIZE(((char *)(bp) - DSIZE)))
#define CURR_SIZE(bp) GET_SIZE(GET_HD(bp)) // 当前块大小
#define NEXT_SIZE(bp) GET_SIZE(GET_HD(GET_NEXT(bp))) // 前驱块大小
#define PREV_SIZE(bp) GET_SIZE(GET_HD(GET_PREV(bp))) // 后继块大小

// 块链表的前驱后继及其 GET 方法
#define PRE(bp) ((char*)(bp) + WSIZE) //块链表前驱
#define SUC(bp) ((char*)bp)  //块链表的后继
#define GET_PRE(bp) (GET(PRE(bp)))
#define GET_SUC(bp) (GET(SUC(bp)))

static void mm_check();
static int is_inlist(void*);
static int check_cycle(void);
static int check_free(void);
static int check_blocks_free(void);

static int index_set(size_t);
static void insert_block(char*);
static void delete_block(char*);
static void *extend_heap(size_t);   // 扩展堆
int mm_init (void);
void *mm_malloc (size_t size);
void mm_free (void *ptr);
void *mm_realloc(void *ptr, size_t size);
static size_t align_size(size_t);
static void *extend_heap(size_t);
static void *coalesce(void *);
static void *find_best_fit(size_t, int);
// static void *find_first_fit(size_t, int);
static void *place(char *, size_t);
/**
 * 初始化内存管理模块
 * 
 * 本函数通过分配和初始化堆内存来启动内存管理模块它首先向系统请求一段内存区域，
 * 然后设置必要的数据结构以跟踪和管理这块内存区域的分配和释放
 * 
 * @return 如果初始化成功，返回0；如果失败，返回-1
 */
int mm_init(void)
{
    // 向系统请求一段内存作为堆列表的起始部分
    heap_list = mem_sbrk((SEG_LEN + 3) * WSIZE);
    // 分配错误
    if(heap_list == (void *) - 1) 
        return -1;
        
    // 初始化空闲块大小类头指针
    int i;
    for(i = 0; i < SEG_LEN; ++i)
        SET(heap_list + i * WSIZE, NULL);

    // 初始化堆列表的起始块，设置其元数据表示该块是已分配的状态
    SET(heap_list + (i+0)*WSIZE, COMBINE(DSIZE, ALLOCATED));  
    SET(heap_list + (i+1)*WSIZE, COMBINE(DSIZE, ALLOCATED));  
    SET(heap_list + (i+2)*WSIZE, COMBINE(0, ALLOCATED));      

     // 对齐
    global_ptr = heap_list;
    heap_list = (char *)ALIGN((size_t)(heap_list + (i + 1) * WSIZE));

    // 扩展空栈
    if(extend_heap(CHUNKSIZE) == NULL){
        // 分配错误
        //mm_check();
        return -1;
    }
    //mm_check();
    return 0;
}


void *mm_malloc(size_t size)
{
    size_t asize = align_size(size); // 调整后的块大小
    size_t extend_size; // 扩展堆大小                  
    char *bp;

    // 空块
    if(size == 0)
        return NULL;

    // 使用BEST FIT
    if((bp = find_best_fit(asize, index_set(asize))) != NULL)
        return place(bp, asize);
    else{
        // fit失败
        extend_size = MAX(asize, CHUNKSIZE);
        if((bp = extend_heap(extend_size)) == NULL)
            return NULL;
        return place(bp, asize);
    }
}

void mm_free(void *ptr)
{
    char *bp = ptr;
    size_t size = CURR_SIZE(bp);

    // 直接设置空闲
    SET(GET_HD(bp), COMBINE(size, FREE));
    SET(GET_FT(bp), COMBINE(size, FREE));

    // 释放同时合并
    coalesce(bp);
}

void *mm_realloc(void *ptr, size_t size)
{
    // ptr 为空，等效于分配新块
    if (ptr == NULL)    
        return mm_malloc(size);
    
    // 请求大小为 0，释放原块并返回 NULL
    if (size == 0) {
        mm_free(ptr);
        return NULL;
    }

    // 对齐到 ALIGNMENT 边界
    size_t aligned_size = align_size(size);
    size_t old_size = CURR_SIZE(ptr); // 获取原块的大小
    char *newptr;

    // 请求大小与原块大小相等，直接返回原块
    if (old_size == aligned_size)
        return ptr;

    // 获取相邻块的分配状态和大小
    size_t prev_alloc = GET_ALLOC(GET_FT(GET_PREV(ptr))); // 前一块的分配状态
    size_t next_alloc = GET_ALLOC(GET_HD(GET_NEXT(ptr))); // 后一块的分配状态
    size_t next_size = NEXT_SIZE(ptr);                   // 后一块的大小
    size_t total_size = old_size;                        // 当前块和可能合并后的总大小
    char *next_bp = GET_NEXT(ptr);                       // 指向后一块的指针

    // case 1：后继块为空闲块且合并后大小足够
    if (prev_alloc && !next_alloc && (old_size + next_size >= aligned_size)) {
        total_size += next_size;                // 更新总大小
        delete_block(next_bp);                  // 移除后继块
        SET(GET_HD(ptr), COMBINE(total_size, ALLOCATED)); // 更新header
        SET(GET_FT(ptr), COMBINE(total_size, ALLOCATED)); // 更新footer
        place(ptr, total_size);                 // 放置新块
    }
    // case 2：后继块为堆尾，需要扩展堆
    else if (!next_size && aligned_size >= old_size) {
        size_t extend_size = aligned_size - old_size; // 需要扩展的堆大小
        void *result = mem_sbrk(extend_size);
        if (result == (void *)-1) {
            // 扩展堆失败
            return NULL;
        }

        // 更新当前块的头部和尾部标记
        SET(GET_HD(ptr), COMBINE(total_size + extend_size, ALLOCATED));
        SET(GET_FT(ptr), COMBINE(total_size + extend_size, ALLOCATED));
        SET(GET_HD(GET_NEXT(ptr)), COMBINE(0, ALLOCATED)); // 更新新的 Epilogue 块
        place(ptr, aligned_size);                          // 放置块
    }
    // case 3：无法就地扩展，分配新的块
    else {
        newptr = mm_malloc(aligned_size); // 分配新块
        if (newptr == NULL)
            return NULL;
        // 将原块的数据拷贝到新块
        memmove(newptr, ptr, MIN(old_size, size));
        mm_free(ptr); // 释放原块
        return newptr;
    }

    // 返回调整后的块指针
    return ptr;
}

static void *extend_heap(size_t asize)
{
    char *bp;

    if((long)(bp = mem_sbrk(asize)) == -1){
        // 分配错误
        return NULL;
    }
    
    // 初始化空闲块的头尾和结尾块的头部 
    SET(GET_HD(bp), COMBINE(asize, FREE)); // 空闲块头部
    SET(GET_FT(bp), COMBINE(asize, FREE)); // 空闲块尾部
    SET(GET_HD(GET_NEXT(bp)), COMBINE(0, ALLOCATED)); //结尾块头部

    return coalesce(bp);
}


static void *coalesce(void *bp)
{
    // 获取分配状态
    size_t prev_alloc = GET_ALLOC(GET_FT(GET_PREV(bp))); // 前一块是否分配
    size_t next_alloc = GET_ALLOC(GET_HD(GET_NEXT(bp))); // 后一块是否分配
    size_t size = CURR_SIZE(bp);                        // 当前块的大小

    if (prev_alloc && next_alloc) {    
        // case 1：前后块都已分配，无法合并
        insert_block(bp); // 当前块插入空闲链表
        return bp;
    }
    else if (prev_alloc && !next_alloc) {
        // case 2：后块空闲，合并当前块和后块
        size += NEXT_SIZE(bp);           // 更新块大小
        delete_block(GET_NEXT(bp));      // 移除后块
        SET(GET_HD(bp), COMBINE(size, FREE)); // 更新头部
        SET(GET_FT(bp), COMBINE(size, FREE)); // 更新尾部
        SET(PRE(bp), NULL);              // 清空前驱
        SET(SUC(bp), NULL);              // 清空后继
    }
    else if (!prev_alloc && next_alloc) {
        // case 3：前块空闲，合并当前块和前块
        size += PREV_SIZE(bp);           // 更新块大小
        delete_block(GET_PREV(bp));      // 移除前块

        SET(GET_FT(bp), COMBINE(size, FREE)); // 更新尾部
        SET(GET_HD(GET_PREV(bp)), COMBINE(size, FREE)); // 更新前块的头部

        bp = GET_PREV(bp);               // 更新当前块指针为前块
        SET(PRE(bp), NULL);              // 清空前驱
        SET(SUC(bp), NULL);              // 清空后继
    }
    else {
        // case 4：前后块均为空闲块，合并三块
        size += NEXT_SIZE(bp) + PREV_SIZE(bp); // 更新总大小
        delete_block(GET_PREV(bp));           // 移除前块
        delete_block(GET_NEXT(bp));           // 移除后块

        SET(GET_HD(GET_PREV(bp)), COMBINE(size, FREE)); // 更新前块的头部
        SET(GET_FT(GET_NEXT(bp)), COMBINE(size, FREE)); // 更新后块的尾部

        bp = GET_PREV(bp);                   // 更新当前块指针为前块
        SET(PRE(bp), NULL);                  // 清空前驱
        SET(SUC(bp), NULL);                  // 清空后继
    }
    insert_block(bp); // 合并后的块插入空闲链表
    return bp;
}

static size_t align_size(size_t size)
{
    // 调整块大小
    if(size <= DSIZE) return 2*DSIZE;
    else return DSIZE * ((size + (DSIZE) + (DSIZE - 1)) / DSIZE);

    return 0;
}


static void *find_best_fit(size_t size, int seg_idx)
{
    void *best_bp = NULL; // 用于存储最合适的块指针
    size_t min_diff = (size_t)-1; // 用于存储最小的大小差

    // 遍历各个大小类
    while (seg_idx < SEG_LEN) {
        char *root = global_ptr + seg_idx * WSIZE;
        char *bp = (char *)GET_SUC(root);

        // 遍历当前大小类的空闲块链表
        while (bp) {
            size_t blk_size = CURR_SIZE(bp);
            if (blk_size >= size) {
                size_t diff = blk_size - size;
                if (diff < min_diff) {
                    best_bp = bp;
                    min_diff = diff;

                    // 如果差值为0，找到完全匹配的块，可以直接返回
                    if (min_diff == 0)
                        return best_bp;
                }
            }
            bp = (char *)GET_SUC(bp); // 遍历下一个块
        }
        seg_idx++; // 查看下一大小类
    }
    return best_bp; // 返回找到的最合适块，若无匹配则为 NULL
}

static void *find_first_fit(size_t size, int seg_idx)
{
    // First Fit
    while(seg_idx < SEG_LEN){
        char *root = global_ptr + seg_idx * WSIZE;
        char *bp = (char *)GET_SUC(root);
        while(bp){
            if((size_t)CURR_SIZE(bp) >= size)
                return bp;
            
            bp = (char *)GET_SUC(bp);
        }
        // 在这类中未找到适合，在更大类中寻找
        seg_idx++;
    }
    return NULL;
}
static void *place(char *bp, size_t asize)
{
    size_t blk_size = CURR_SIZE(bp); // 当前块的大小
    size_t rm_size = blk_size - asize; // 分配后剩余的空间大小

    // 当前块未分配，从空闲链表中移除
    if (!GET_ALLOC(GET_HD(bp)))
        delete_block(bp);

    // 剩余空间足够大
    if (rm_size >= 2 * DSIZE) {
        if (asize > 64) {
            // 如果分配大小大于 64 字节，优先将剩余部分作为空闲块
            SET(GET_HD(bp), COMBINE(rm_size, FREE)); // 设置剩余块为空闲块
            SET(GET_FT(bp), COMBINE(rm_size, FREE));
            SET(GET_HD(GET_NEXT(bp)), COMBINE(asize, ALLOCATED)); // 设置分配块为已分配
            SET(GET_FT(GET_NEXT(bp)), COMBINE(asize, ALLOCATED));

            insert_block(bp); // 将剩余的空闲块插入空闲链表
            return GET_NEXT(bp); // 返回已分配块的指针
        } else {
            // 分配大小小于等于 64 字节，优先将当前块分割
            SET(GET_HD(bp), COMBINE(asize, ALLOCATED)); // 设置当前块为已分配
            SET(GET_FT(bp), COMBINE(asize, ALLOCATED));
            SET(GET_HD(GET_NEXT(bp)), COMBINE(rm_size, FREE)); // 设置剩余块为空闲
            SET(GET_FT(GET_NEXT(bp)), COMBINE(rm_size, FREE));

            coalesce(GET_NEXT(bp)); // 合并新生成的空闲块
        }
    }
    else {
        // 剩余空间不足以分割，直接将整个块分配
        SET(GET_HD(bp), COMBINE(blk_size, ALLOCATED)); // 标记整个块为已分配
        SET(GET_FT(bp), COMBINE(blk_size, ALLOCATED));
    }

    return bp;
}



// 假设这些函数已经定义
int check_cycle(void);
int check_free(void);
int check_blocks_free(void);

// 日志宏定义
#define LOG_ERROR(fmt, ...) fprintf(stderr, "Error: " fmt "\n", ##__VA_ARGS__)
#define LOG_INFO(fmt, ...) fprintf(stdout, fmt "\n", ##__VA_ARGS__)

// 错误处理函数
void handle_error(const char *msg) {
    LOG_ERROR("%s", msg);
}

static void mm_check(void) {
    // 快慢指针检测循环链表
    if (check_cycle()) {
        handle_error("Free list contains a cycle.");
        return;
    }

    // 检查所有空闲块是否在链表中
    if (!check_free()) {
        handle_error("Some free blocks aren't in the free list.");
        return;
    }

    // 检查所有链表块是否空闲
    if (!check_blocks_free()) {
        handle_error("Some blocks in the free list are not marked as free.");
        return;
    }

    LOG_INFO("Heap check passed.");
}

static int is_inlist(void *bp) {
    void *cur = heap_list;

    while (cur != NULL) {
        if (cur == bp) {                 
            return 1;
        }
        cur = GET_NEXT(cur);
    }
    return 0;                              
}


// 检查堆中所有空闲块是否在链表中
static int check_free(void) {
    void *bp = heap_list;

    while (GET_SIZE(GET_HD(bp)) > 0) {        // 遍历整个堆
        if (!GET_ALLOC(GET_HD(bp))) {         // 如果块是空闲的
            if (!is_inlist(bp)) {     // 检查是否在链表中
                return 0;
            }
        }
        bp = GET_NEXT(bp);
    }
    return 1;
}
static int check_cycle(void) {
    void *slowPointer = heap_list;
    void *fastPointer = heap_list;

    while (fastPointer != NULL && GET_NEXT(fastPointer) != NULL) {
        slowPointer = GET_NEXT(slowPointer);              // 慢指针前进一步
        fastPointer = GET_NEXT(GET_NEXT(fastPointer));    // 快指针前进两步

        if (slowPointer == fastPointer) {                 // 快慢指针相遇
            return 1;
        }
    }
    return 0;
}

// 检查空闲链表中的每个块是否是空闲的
static int check_blocks_free(void) {
    void *currentBlock = heap_list;

    while (currentBlock != NULL) {
        if (GET_ALLOC(GET_HD(currentBlock))) {          // 如果链表中的块不是空闲的
            return 0;
        }
        currentBlock = GET_NEXT(currentBlock);
    }
    return 1;
}

static int index_set(size_t blockSize) 
{
    size_t offset, shift;

    // 快速计算二进制表示下的最高有效位（参考Stanford算法）
    offset = (blockSize > 0xFFFF)   << 4; blockSize >>= offset;             // 如果块大小大于 2^16，则偏移 16 位
    shift = (blockSize > 0xFF) << 3; blockSize >>= shift; offset |= shift; // 如果块大小大于 2^8，则偏移 8 位
    shift = (blockSize > 0xF)  << 2; blockSize >>= shift; offset |= shift; // 如果块大小大于 2^4，则偏移 4 位
    shift = (blockSize > 0x3)  << 1; blockSize >>= shift; offset |= shift; // 如果块大小大于 2^2，则偏移 2 位
    offset |= (blockSize >> 1);                                // 计算最终索引偏移量

    // 计算从 2^4 开始的大小类索引（最小块为 16 字节）
    int index = (int)offset - 4; // 对数值减去基准偏移（4 对应于 16 字节）
    if (index < 0) 
        index = 0;          // 如果小于最小索引，将其限制为 0
    if (index >= SEG_LEN) 
        index = SEG_LEN - 1; // 如果超出最大分段数，将其限制为最大索引

    return index;
}

/**
 * 将空闲块插入到分离链表中
 * 
 *指向待插入空闲块的指针
 * 
 * 该函数根据当前空闲块的大小确定其应该插入的分离链表的索引，并将空闲块插入到相应的链表中
 * 插入操作会根据地址大小保持链表中的块按地址有序排列
 */
static void insert_block(char *fbp)
{
    // 确定大小类索引
    int seg_index = index_set(CURR_SIZE(fbp));
    // 获取对应分离链表的根节点
    char *root = global_ptr + seg_index * WSIZE;

    // 地址排序插入
    void *suc = root;  // 当前遍历的节点，初始化为根节点

    // 寻找插入位置
    while (GET_SUC(suc)) {
        suc = (char *)GET_SUC(suc);
        // 找到插入位置
        if ((unsigned int)suc >= (unsigned int)fbp) {
            char *tmp = suc;  // 保存当前节点
            suc = (char *)GET_PRE(suc);  // 获取插入位置的前驱节点

            // 更新前驱和后继的指针
            SET(SUC(suc), fbp);  // 前驱的后继指向新块
            SET(PRE(fbp), suc);  // 新块的前驱指向前驱
            SET(SUC(fbp), tmp);  // 新块的后继指向后继
            SET(PRE(tmp), fbp);  // 后继的前驱指向新块
            return;
        }
    }

    // 当前大小类链表为空或新块地址大于链表中的所有块
    SET(SUC(suc), fbp);  // 设置最后一个节点的后继为新块
    SET(PRE(fbp), suc);  // 新块的前驱指向最后一个节点
    SET(SUC(fbp), NULL); // 新块的后继为空
}


static void delete_block(char *fbp)
{
    // 如果前驱和后继均存在（即块在链表中间）
    if (GET_SUC(fbp) && GET_PRE(fbp)) {
        if (GET_PRE(fbp) != NULL && GET_SUC(fbp) != NULL) {
            SET(SUC(GET_PRE(fbp)), GET_SUC(fbp)); // 前驱的后继指向当前块的后继
            SET(PRE(GET_SUC(fbp)), GET_PRE(fbp)); // 后继的前驱指向当前块的前驱
        }
    }
    else if (GET_PRE(fbp)) { // 当前块是链表末尾块
        if (GET_PRE(fbp) != NULL) {
            SET(SUC(GET_PRE(fbp)), NULL); // 前驱的后继置为空
        }
    }
    else if (GET_SUC(fbp)) { // 当前块是链表头部块
        if (GET_SUC(fbp) != NULL) {
            SET(PRE(GET_SUC(fbp)), NULL); // 后继的前驱置为空
        }
    }

    SET(SUC(fbp), NULL);
    SET(PRE(fbp), NULL);
}